package org.lql.algo.codecrush.hot100.linked;

import org.lql.algo.common.ListNode;

import java.util.PriorityQueue;

/**
 * @author: liangqinglong
 * @date: 2025-10-10 21:34
 * @description: 23. 合并 K 个升序链表 <a href="https://leetcode.cn/problems/merge-k-sorted-lists/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class MergeKLists {

	public ListNode mergeKLists(ListNode[] lists) {
		if (lists.length == 0) {
			return null;
		}
		PriorityQueue<Node> queue = new PriorityQueue<>((a, b) -> a.val - b.val);
		for (ListNode list : lists) {
			if (list != null) {
				queue.offer(new Node(list.val, list));
			}
		}
		ListNode dummy = new ListNode(0);
		ListNode cur = dummy;
		while (!queue.isEmpty()) {
			Node node = queue.poll();
			cur.next = node.node;
			cur = cur.next;
			ListNode next = node.node.next;
			if (next != null) {
				queue.offer(new Node(next.val, next));
			}
		}
		return dummy.next;
	}


	static class Node {
		int val;
		ListNode node;

		Node(int x, ListNode node) {
			this.val = x;
			this.node = node;
		}
	}

	public static void main(String[] args) {
		MergeKLists mergeKLists = new MergeKLists();
		ListNode listNode1 = new ListNode(1);
		listNode1.next = new ListNode(4);
		listNode1.next.next = new ListNode(5);
		ListNode listNode2 = new ListNode(1);
		listNode2.next = new ListNode(3);
		listNode2.next.next = new ListNode(4);
		ListNode listNode3 = new ListNode(2);
		listNode3.next = new ListNode(6);
		ListNode listNode = mergeKLists.mergeKLists(new ListNode[]{listNode1, listNode2, listNode3});
		while (listNode != null) {
			System.out.print(listNode.val + " ");
			listNode = listNode.next;
		}
	}
}
